# 有序数组转成二叉搜索树

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
    # 这个结果是不唯一的
    def helper(left, right):
        if left > right:    return None
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = helper(left, mid - 1)
        root.right = helper(mid + 1, right)
        return root

    return helper(0, len(nums) - 1)

# 高度平衡二叉搜索树指两边的高度相差不超过1的树。有序数组构建二叉搜索树肯定是需要用到递归的
# 递归就要想到最简单的情况。最简单的情况是一个根节点，一个左子树、右子树(当然也可以没有);根节点是中间的数，左子树是左边的，右子树是右边的
# 上述建立的高度平衡二叉搜索树一定不是唯一的。

# 这个网上说的三种方法分别是每次递归中间左边第一个作为根节点。中间右边第一个作为根节点。随机选择左右边第一个作为根节点
